package LeetCode精选TOP面试题;

public class p53最大子数组和 {
    public int maxSubArray(int[] nums) {
        if (nums.length==1) {
            return nums[0];
        }

        int[] findMaxSum=new int[nums.length];
        findMaxSum[0]=nums[0];
        int maxNum=findMaxSum[0];

        for (int i = 1; i <nums.length; i++) {
            if (findMaxSum[i-1]>=0) {
                //如果findMaxSum[i-1]的元素 >= 0,就将nums[i]+findMaxSum[i-1]存储到 findMaxSum[i]中
                findMaxSum[i]=nums[i]+findMaxSum[i-1];
            }else {
                //如果findMaxSum[i-1]的元素 < 0,就将 nums[i]直接存储到 findMaxSum[i]中
                findMaxSum[i]=nums[i];
            }

            //更新当前的最大和
            if (maxNum<findMaxSum[i]) {
                maxNum=findMaxSum[i];
            }
        }
        return maxNum;
    }
}
